5.32

题目

Prove that the following two languages are undecidable.

b. PREFIX-FREE $_{CFG}$ = ${⟨ G ⟩ ∣ G is a CFG where L (G) is prefix-free}$ .

思路

点击展开

对 5.21 略作修改，让骨牌匹配等价于找到 CFG 的一个字符串是另一个字符串的前缀

解答

点击展开

对 5.21 的 Hint 修改，增加 $a_{0}$ ，调整 $a_{i}$ 的位置，结果如下：

Given an instance

P = {[\frac{t_{1}}{b_{1}}], [\frac{t_{2}}{b_{2}}], \dots, [\frac{t_{k}}{b_{k}}]}

of the Post Correspondence Problem, construct a CFG $G$ with the rules

S \to T ∣ B a_{0}

T \to a_{1} T t_{1} ∣ \dots ∣ a_{k} T t_{k} ∣ a_{1} # t_{1} ∣ \dots ∣ a_{k} # t_{k}

B \to a_{1} B b_{1} ∣ \dots ∣ a_{k} B b_{k} ∣ a_{1} # b_{1} ∣ \dots ∣ a_{k} # b_{k}

where $a_{0}, a_{1}, \dots, a_{k}, #$ are new terminal symbols.

如果存在骨牌匹配，即 $b_{1} b_{2} \dots b_{k} = t_{1} t_{2} \dots t_{k}$ ，那么 $a_{1} a_{2} \dots a_{k} # t_{k} \dots t_{2} t_{1}$ 是 $a_{1} a_{2} \dots a_{k} # b_{k} \dots b_{2} b_{1} a_{0}$ 的前缀，且两者均在 $L (G)$ 中

反之，如果存在 $L (G)$ 中的相异字符串 M 是 N 的前缀， $a_{1} a_{2} \dots a_{k} #$ 部分必须相同，这代表 M 和 N 分别由 T 和 B 生成，否则 M 和 N 相同。进而， $b_{1} b_{2} \dots b_{k} = t_{1} t_{2} \dots t_{k}$